//
// Created by francklinson on 2021/5/25.
//

/*
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表
（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

输入：[1,2,3,4,5,null,7,8]

        1
       /  \
      2    3
    / \    \
    4   5    7
   /
  8

输出：[[1],[2,3],[4,5,7],[8]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/list-of-depth-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
// bfs
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    vector<ListNode *> listOfDepth(TreeNode *tree) {
        vector<ListNode *> ans;
        if (tree == nullptr) return ans;
        queue<pair<TreeNode *, int>> q;
        q.emplace(tree, 0);
        int curDepth = 0;
        while (!q.empty()) {
            auto f = q.front();
            q.pop();
            // 子节点入队
            if (f.first->left != nullptr) q.emplace(f.first->left, f.second + 1);
            if (f.first->right != nullptr) q.emplace(f.first->right, f.second + 1);
            // 首节点放入结果链表
            if (f.second != curDepth) { // 新增一条链表
                ++curDepth;
                ans.push_back(new ListNode(f.first->val));
            } else {
                if (ans.empty()) ans.push_back(new ListNode(f.first->val)); // 根节点
                else {  // 放到链表尾部
                    auto frontNode = ans.back();
                    while (frontNode->next != nullptr) frontNode = frontNode->next;
                    frontNode->next = new ListNode(f.first->val);
                }
            }
        }
        return ans;

    }
};

class Solution2 {
public:
    vector<ListNode *> listOfDepth(TreeNode *tree) {
        // 返回的结果
        vector<ListNode *> res;
        if (tree == nullptr) {
            return res;
        }
        queue<TreeNode *> q;
        q.push(tree);

        while (!q.empty()) {
            ListNode *head = nullptr;
            ListNode *prev = nullptr;
            // 只遍历当前层的大小
            int currSize = q.size();
            for (int i = 0; i < currSize; ++i) {
                TreeNode *currNode = q.front();
                auto newNode = new ListNode(currNode->val);
                q.pop();
                // 这里需要考虑链表首结点和构建
                if (head == nullptr) {
                    head = newNode;
                } else {
                    prev->next = newNode;
                }
                prev = newNode;

                if (currNode->left != nullptr) {
                    q.push(currNode->left);
                }
                if (currNode->right != nullptr) {
                    q.push(currNode->right);
                }
            }
            res.push_back(head);
        }

        return res;
    }
};

int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(2), n3 = TreeNode(3), n4 = TreeNode(4), \
 n5 = TreeNode(5), n6 = TreeNode(6), n7 = TreeNode(7), n8 = TreeNode(8);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n7;
    n4.left = &n8;
    Solution2 sol;
    auto ans = sol.listOfDepth(&n1);
    for (auto &x:ans) {
        while (x != nullptr) {
            cout << x->val << endl;
            x = x->next;
        }
        cout << "---" << endl;
    }
    return 0;
}